package main

import "fmt"

/*
*
方法1: 直接排序
方法2: 利用quickselect

	第k大的数就等于第len(nums)-k+1小的数，也就是从小到大排列下标为len(nums)-k（以下用t来表示）的数
	我们利用partiion可以将数组（此时查询范围lo=0,hi=len(nums)-1）分割为3部分 0~p-1部分 p p+1~len(nums)-1部分
		如果t==p，则表示位置p就是第k大的数，直接返回nums[p]
		如果t<p,则表示t存在于0~p-1区间内，将hi设置为p-1,重新查询0~p-1区间，反复执行,直至t==p
		如果t>p,则表示t存在于p+1~len(nums)-1区间内，将lo设置为p+11,重新查询p+1~len(nums)-1区间，反复执行,直至t==p
	时间复杂度
		最快O(n) 最慢O(n^2)
		ps: 最快情况进行一次遍历查找p==t，O(n)

方法3: 利用小根堆

参考:

	https://www.youtube.com/watch?v=zyskis1Gw0c
	https://www.cnblogs.com/grandyang/p/4539757.html
	https://github.com/halfrost/LeetCode-Go/blob/master/Algorithms/0215.%20Kth%20Largest%20Element%20in%20an%20Array/215.%20Kth%20Largest%20Element%20in%20an%20Array.go
*/
func main() {
	fmt.Println(findKthLargest([]int{1}, 1))
}

/* 解法1
func findKthLargest(nums []int, k int) int {
	if len(nums) == 0 {
		return 0
	}
	sort.Ints(nums)
	return nums[len(nums)-k]
}
*/

// 解法2
func findKthLargest(nums []int, k int) int {
	if len(nums) == 0 {
		return 0
	}

	if len(nums) == 1 {
		return nums[0]
	}

	t := len(nums) - k //最大的第k个数等于最小的第len(nums)-k个数

	lo := 0
	hi := len(nums) - 1
	for {
		if lo > hi {
			break
		}
		p := partition(nums, lo, hi)
		if p == t {
			return nums[p]
		} else if p < t {
			lo = p + 1
		} else {
			hi = p - 1
		}
	}

	return 0
}

// Lomuto partition（洛穆托分区法）
// partition 返回的是 升序下标
func partition(nums []int, lo int, hi int) int {
	i := lo - 1
	for j := lo; j < hi; j++ {
		if nums[j] < nums[hi] {
			i++
			nums[i], nums[j] = nums[j], nums[i]
		}
	}

	nums[i+1], nums[hi] = nums[hi], nums[i+1]
	return i + 1
}
